UVa/406 - Prime cuts/406.cpp

   1 #include <iostream>
   2 #include <vector>
   3
   4 using namespace std;
   5
   6 const int SIZE = 1000;
   7
   8 //criba[i] = false si i es primo
   9 bool criba[SIZE+1];
  10
  11 void buildCriba(){
  12   memset(criba, false, sizeof(criba));
  13
  14   criba[0] = criba[1] = true;
  15   for (int i=2; i<=SIZE; i += 2){
  16     criba[i] = true;
  17   }
  18
  19   for (int i=3; i<=SIZE; i += 2){
  20     if (!criba[i]){
  21       for (int j=i+i; j<=SIZE; j += i){
  22         criba[j] = true;
  23       }
  24     }
  25   }
  26 }
  27
  28 int main(int argc, char const *argv){
  29   vector<int> primes;
  30   primes.push_back(1);
  31   primes.push_back(2);
  32   buildCriba();
  33   for (int i=3; i<=SIZE; i+=2){
  34     if (!criba[i]){
  35       primes.push_back(i);
  36     }
  37   }
  38
  39   //cout << "primes.size() " << primes.size() << endl;
  40   //cout << "Last: " << primes.back() << endl;
  41   int n, c;
  42   while (cin >> n >> c){
  43     int end = 0;
  44     while (end < primes.size() && primes[end] <= n){
  45       ++end;
  46     }
  47     --end;
  48     //La lista termina en end, inclu铆do. Tiene end+1 elementos.
  49     //cout << primes[end] << endl;
  50     int a, b; //imprimir desde primes[a] hasta primes[b]
  51     if ((end+1)%2 == 0){ //tiene cantidad par de elementos
  52       //cout << "Cantidad par" << endl;
  53       a = end/2 - (c-1);
  54       if (a < 0) a = 0;
  55       b = end/2 + c;
  56       if (b > end) b = end;
  57     }else{ //tiene cantidad impar
  58       //cout << "Cantidad impar" << endl;
  59       a = (end+1)/2 - (c-1);
  60       if (a < 0) a = 0;
  61       b = (end+1)/2 + (c-1);
  62       if (b > end) b = end;
  63     }
  64
  65     cout << n << " " << c << ":";
  66     for (int i=a; i<=b; ++i){
  67       cout << " " << primes[i];
  68     }
  69     cout << endl << endl;
  70   }
  71   return 0;
  72 }
  73